package binary_search

// 旋转数组的最小数字
// 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素
// 例如：输入{3,4,5,1,2} 为{1,2,3,4,5}的一个旋转，该数组的最小数字为1

func SpinArrayMinSearch(a []int) int {
	if len(a) == 0 {
		return -1
	}

	var index1 = 0
	var index2 = len(a) - 1
	var indexMid = index1
	for a[index1] >= a[index2] {
		if index2-index1 == 1 {
			indexMid = index2
			break
		}
		indexMid = (index1 + index2) / 2
		// 如果下标位index1 index2和indexMid指向的三个数字相等
		// 则只能顺序查找
		if a[index1] == a[index2] && a[indexMid] == a[index1] {
			return minInOrder(a, index1, index2)
		}

		if a[indexMid] >= a[index1] {
			index1 = indexMid
		} else if a[indexMid] <= a[index2] {
			index2 = indexMid
		}
	}
	return a[indexMid]
}

func minInOrder(a []int, index1, index2 int) int {
	var result = a[index1]
	for i := index1 + 1; i <= index2; i++ {
		if result > a[i] {
			result = a[i]
		}
	}
	return result
}
